package 堆;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class 面试题1714最小K个数 {
    public int[] smallestK(int[] arr, int k) {
        //创建数组保存前k个元素
        int[] ret = new int[k];
        if (arr.length == 0 || k == 0) {
            return ret;
        }
        //JDK默认为最小堆，创建一个最小堆，如果堆中元素不够K个直接入堆，否则判断最后一个元素和要入堆元素的大小关系
        //如果入堆元素小，则替换掉最后一个元素，然后入堆，否则继续循环

        //lambda表示式写法,函数式编程
//        Queue<Integer> queue = new PriorityQueue<>((o1,o2) -> o2 - o1);


        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });//PriorityQueue优先级队列
        for (int i = 0; i < arr.length; i++) {
            if (queue.size() < k) {
                queue.offer(arr[i]);
            }else {
                //队列已满K个元素
                int max = queue.peek();
                if (queue.peek() <= arr[i]) {
                    continue;
                } else {
                    queue.poll();
                    queue.offer(arr[i]);
                }
            }
        }
        int i = 0;
        while (!queue.isEmpty()) {
            ret[i++] = queue.poll();
        }
        return ret;
    }
}
